DZY Loves Sorting

DZY has a sequence $a[1..n]$. It is a permutation of integers $1 \sim n$.

Now he wants to perform two types of operations:

$0 \,\,l \,\,r$: Sort $a[l..r]$ in increasing order.

$1\,\, l \,\,r$: Sort $a[l..r]$ in decreasing order.

After doing all the operations, he will tell you a position $k$, and ask you the value of $a[k]$.

First line contains $t$, denoting the number of testcases.

$t$ testcases follow. For each testcase:

First line contains $n,m$. $m$ is the number of operations.

Second line contains $n$ space-separated integers $a[1],a[2],\cdots,a[n]$, the initial sequence. We ensure that it is a permutation of $1\sim n$.

Then $m$ lines follow. In each line there are three integers $opt,l,r$ to indicate an operation.

Last line contains $k$.

($1\le t \le 50,1\le n,m \le 100000,1\le k \le n, 1\le l\le r\le n, opt \in \{0,1\}$. Sum of $n$ in all testcases does not exceed $150000$. Sum of $m$ in all testcases does not exceed $150000$)

For each testcase, output one line - the value of $a[k]$ after performing all $m$ operations.

1
6 3
1 6 2 5 3 4
0 1 4
1 3 6
0 2 4
3

5

1 6 2 5 3 4 -> [1 2 5 6] 3 4 -> 1 2 [6 5 4 3] -> 1 [2 5 6] 4 3. At last $a[3]=5$.

BestCoder Round #76 (div.1)